package game;

/**
 * 给定一个二维数组matrix，每个单元都是一个整数，有正有负。最开始的时候小Q操纵一条长度为0的蛇蛇从矩阵最左侧任选一个单元格进入地图，蛇每次只能够到达当前位置的右上相邻，右侧相邻和右下相邻的单元格。蛇蛇到达一个单元格后，自身的长度会瞬间加上该单元格的数值，任何情况下长度为负则游戏结束。小Q是个天才，他拥有一个超能力，可以在游戏开始的时候把地图中的某一个节点的值变为其相反数（注:最多只能改变一个节点）。问在小Q游戏过程中，他的蛇蛇最长长度可以到多少?
 * 比如:
 * 1 -4 10
 * 3 -2 -1
 * 2 -1 0
 * 0 5 -2
 * 最优路径为从最左侧的3开始，3 ->-4(利用能力变成4) ->10。所以返回17。
 *
 * @author Liaorun
 */
public class SnakeGame {

    public static void main(String[] args) {
        int[][] matrix = {{-100, -4000, -10000}, {-200, -2000, -100000}, {-300, -1000, -60000}, {-2000, -5000, -20000000},};

        System.out.println(walk1(matrix));
        System.out.println(snake(matrix));
    }


    public static int walk1(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int res = Integer.MIN_VALUE;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                int[] ans = process(matrix, i, j);
                res = Math.max(res, Math.max(ans[0], ans[1]));
            }
        }
        return res;
    }

    public static class Info {
        /**
         * 蛇蛇不使用能力的情况能获取的最大分数
         */
        public int no;
        /**
         * 蛇蛇使用能力的情况能获取的最大分数
         */
        public int yes;

        public Info(int no, int yes) {
            this.no = no;
            this.yes = yes;
        }
    }

    public static int snake(int[][] matrix) {
        int ans = Integer.MIN_VALUE;
        Info[][] dp = new Info[matrix.length][matrix[0].length];
        for (int row = 0; row < matrix.length; row++) {
            for (int col = 0; col < matrix[0].length; col++) {
                Info info = process1(matrix, row, col, dp);
                ans = Math.max(ans, Math.max(info.no, info.yes));
            }
        }

        return ans;
    }

    public static Info process1(int[][] matrix, int row, int col, Info[][] dp) {

        if (dp[row][col] != null) {
            return dp[row][col];
        }

        // base case,在最左列，没有前置路径
        if (col == 0) {
            dp[row][col] = new Info(matrix[row][col], -matrix[row][col]);
            return dp[row][col];
        }

        // 没有在最左列
        // 我之前的路程中，一次能力也没用，能达到的最大路径和
        int preNo = -1;
        // 我之前的路程中，用过一次能力，能达到的最大路径和
        int preYes = -1;

        // 1.蛇蛇从左上角来的情况
        if (row > 0) {
            // 当前位置不在第一行，则存在左上架的位置
            Info leftUp = process1(matrix, row - 1, col - 1, dp);

            if (leftUp.no >= 0) {
                // 蛇按照规则不能为负的情况下，能不用能力走到左上架
                preNo = leftUp.no;
            }
            if (leftUp.yes >= 0) {
                preYes = leftUp.yes;
            }
        }
        // 2.蛇蛇从左边来的情况
        Info left = process1(matrix, row, col - 1, dp);
        if (left.no >= 0) {
            preNo = Math.max(preNo, left.no);
        }

        if (left.yes >= 0) {
            preYes = Math.max(preNo, left.yes);
        }

        // 3.蛇蛇从左下角来的情况
        if (row < matrix.length - 1) {
            Info leftDown = process1(matrix, row + 1, col - 1, dp);
            if (leftDown.no >= 0) {
                preNo = Math.max(preNo, leftDown.no);
            }

            if (leftDown.yes >= 0) {
                preYes = Math.max(preNo, leftDown.yes);
            }
        }

        // 等到了前面路径的值，需要加工出到当前节点的情况值


        // 到当前位置的路程中，一次能力也没用，能达到的最大路径和
        int no = -1;
        // 到当前位置的路程中，用过一次能力，能达到的最大路径和
        int yes = -1;

        if (preNo >= 0) {
            no = preNo + matrix[row][col];
            yes = preNo + (-matrix[row][col]);
        }

        if (preYes >= 0) {
            yes = Math.max(yes, preYes + matrix[row][col]);
        }

        dp[row][col] = new Info(no, yes);
        return dp[row][col];
    }

    private static int[] process(int[][] matrix, int i, int j) {
        if (j == 0) {
            return new int[]{matrix[i][j], -matrix[i][j]};
        }
        int[] preAns = process(matrix, i, j - 1);
        int preUnuse = preAns[0];
        int preUse = preAns[1];

        if (i - 1 >= 0) {
            preAns = process(matrix, i - 1, j - 1);
            preUnuse = Math.max(preUnuse, preAns[0]);
            preUse = Math.max(preUse, preAns[1]);
        }
        if (i + 1 < matrix.length) {
            preAns = process(matrix, i + 1, j - 1);
            preUnuse = Math.max(preUnuse, preAns[0]);
            preUse = Math.max(preUse, preAns[1]);
        }

        // preUnUse 之前的旅程，没有用过能力
        // preUse 之前的旅程，用过能力

        // 之前没使用过能力，当前位置也不使用的最优解
        int no = -1;
        // 之前没使用过能力，当前位置使用能力的最优解
        int yes = -1;

        if (preUnuse >= 0) {
            no = matrix[i][j] + preUnuse;
            yes = -matrix[i][j] + preUnuse;
        }
        if (preUse >= 0) {
            yes = Math.max(yes, matrix[i][j]);
        }
        return new int[]{no, yes};
    }
}
